Electronic signature mechanisms have been developed for authenticating the source of a document transmitted via telecommunications means. It should be noted that the term “transmission in electronic form” is routinely used to refer to the transmission of a document via telecommunications means. In the context of the invention, the documents in question are necessarily in digital form, as opposed to paper form; the term “message” as used below in this application refers to this type of document. The most widely used electronic signature mechanisms are based on public key cryptographic techniques that rely on an entity known as a trusted authority. The trusted authority usually generates certificates on behalf of users of standard public key methods; these certificates establish a connection between a public key and the identity of the proprietor of the key. To use this kind of method, the persons signing messages must first obtain certification from the trusted authority by communicating thereto at least their public keys and their identities. The method calculates an electronic signature for a message taking account of the content of the message and of the person's private key. The signatory sends the message, the signature and the certificate to the addressee of the message, who verifies the electronic signature of the message using at least the public key and the content of the message.
For some applications, such as electronic voting, electronic bidding or anonymous electronic payments, it is necessary to use an anonymous electronic signature. An anonymous electronic signature has the same characteristics as an ordinary electronic signature except that the addressee cannot determine the identity of the signatory, who remains anonymous. However, the addressee is able to contact the trusted authority, which is able to remove the anonymity by referring to the certificate.
The anonymous group signature is one particular type of anonymous signature. An anonymous group signature scheme enables each member of a group to produce an electronic signature that is characteristic of the group. The addressee of a message accompanied by an anonymous group signature is able to verify that the signature was applied by one of the members of the group but is not able to determine which of the members of the group this was.
In the context of the invention, a group is a set of persons who declare themselves to an authority as belonging to the same group. At the time of this declaration, each person interacts with the trusted authority using a particular protocol, after which the person obtains a private key which is associated with a public key of the group previously determined by the trusted authority, and the authority and the person obtain an identifier of the person associated with the private key. Below, in this application, each person is referred to as a member. One example of a protocol of this kind is described in the paper by J. Camenisch and M. Michels “Efficient Group Signature Schemes For Large Groups”, in B. Kaliski, editor, Advances In Cryptology—CRYPT097, Volume 1296 of LNCS, pages 410 to 424, Springer-Verlag, 1997. The same interaction occurs upon the arrival of a new member. From the point of view of the trusted authority, the existence of a group is reflected by assigning the group a group public key and assigning each member a different private key associated with the public key and an identifier. Using his or her own private key, a member is able to apply an anonymous group signature to a selected message. Any addressee is able to verify that the signature was in fact applied by one of the members of the group, provided that the group public key was used. After verification, the addressee is certain either that the signature was applied by a member of the group or that it was not, as the case may be, but obtains no information as to the identifier of that member, the signatory communicating his or her own identifier to the addressee only in a form encrypted by means of a public key of the trusted authority; the signature is anonymous. However, the addressee may contact the trusted authority, which is able to determine the identity of the signatory from the encrypted identifier accompanying the group anonymous signature. Thus the trusted authority is able to remove the anonymity at any time.
A group may evolve after it has been set up by the trusted authority. A first type of change is for new persons to become members of the group. A second type of change, referred to as revocation, is for members to leave the group or to be excluded from the group. Each time the group changes, the trusted authority is faced with the problem of assigning to or withdrawing from a member of the group the means for applying a group anonymous signature. The first problem that arises relates to assigning a new member the means for applying a group anonymous signature, and is solved using one of the prior art public key/private key generation algorithms that associate as many private keys as necessary with the same public key. One example of this kind of algorithm is described in the paper by J. Camenisch and M. Michels “Efficient Group Signature Schemes For Large Groups”, in B. Kaliski, editor, Advances In Cryptology—CRYPT097, Volume 1296 of LNCS, pages 410 to 424, Springer-Verlag, 1997.
The second problem that arises relates to withdrawing these means from a person, and is solved by various prior art revocation methods.
A first of these methods is described in the paper by E. Bresson and J. Stern “Efficient Revocation In Group Signatures”, in K. Kim, editor, Public Key Cryptography—PKC 2001, Volume 1992 of LNCS, pages 190-206, Springer-Verlag, 2001. That method is based on the fact that each member of a group has a personal identifier. Given that the signature must remain anonymous, it is not possible to reveal this identifier. However, in this method, the identifier of the signatory is divided by that of each revoked member; the result of each division is different from 1 if, and only if, the signatory is not a revoked member. Using an encryption algorithm, each of the results of these divisions is then encrypted and the encrypted result is sent to the addressee, accompanied by particular elements. The addressee uses the particular elements and the encrypted results to verify that the divisions have been effected correctly and that all the results are different from 1, which confirms that the signature was applied by a non-revoked member.
Given that there are as many encrypted results and particular elements as there are revoked members, this method has the drawback of generating a group anonymous signature whose length and calculation time increase in proportion to the number of revoked members.
A second revocation method is described in the paper by H. J. Kim, J. I. Lim and D. H. Lee “Efficient And Secure Member Deletion In Group Signature Schemes”, in D. Won, editor, Information Security And Cryptology—ICISC 2000, Volume 2015 of LNCS, pages 150 et seq., Springer-Verlag, 2000. That method uses three keys in addition to the keys necessary for a successful group signature scheme, namely an ownership private key for each member, an ownership public key to enable members to verify the validity of their own keys, and a renewal public key to enable members to modify their ownership private keys each time that a member joins or leaves the group. The trusted authority modifies the ownership public key and the renewal key for each new member and for each revocation of a member. The remaining members of the group modify their ownership private keys using the renewal key and verifies validity by using the ownership public key. To sign a message electronically, signatory members use their own ownership private keys. Thus the addressee is able to verify the electronic signature using the ownership public key. That method has the drawback of being specific in application, in that it has proven to be secure only in a particular group signature scheme that corresponds to that described in the paper by J. Camenisch and M. Michels “A Group Signature Scheme With Improved Efficiency”, in K. Ohta and D. Pei, editors, Advances In Cryptology—ASIACRYPT'98, Volume 1514 of LNCS, pages 160-174, Springer-Verlag, 1998. Furthermore, that method has the disadvantage that it imposes calculations on each member each time that a member joins or leaves the group; these calculations may become frequent if the dynamics of the group are particularly intense.